1. Field of the Invention
This invention relates generally to network processor-based devices, and more specifically to a single hierarchy independent routing table and packet routing methodology.
2. Discussion of the Prior Art
Currently, network processor-based devices that perform packet routing functions maintain multiple packet routing tables. For instance, as illustrated in FIG. 1, internet routers providing normal IP forwarding and External Border Gateway Protocol Next Hop Features are typically provided with router look-up tables including: 1) an External Border Gateway Protocol table 10 for controlling flow into and out of autonomous networks; and, 2) a packet forwarding table (Next Hop Feature table) 20 for listing subnet addresses 22 and subsequent xe2x80x9cnext hopxe2x80x9d addresses 25 for all routers connected in the autonomous network. More particularly, the BGP tables 10 are maintained on all routers and include subnet addresses 12 for other routers on external networks. The BGP router function particularly, is what is seen by outside networks and is the router that connects an autonomous network to independent external networks.
FIG. 2 identifies an example network 50 comprising an autonomous network 30 and external networks 40a,b interconnected via routers R and network links. In operation, System A (32) in the autonomous network 30 is to forward a packet to a System 1 (34) in external network 40a at an ISO layer three network protocol destination address, e.g., IP address 9.1.1.1. In the forwarding path, router R5 would perform a first lookup in its BGP Lookup table 10 (FIG. 1) to determine whether the path to System 1 (34) destination 9.1.1.1 goes through an exit router and, if so, determines the IP address of the egress interface for that exit router. In the example network of FIG. 1, this BGP egress interface is at address 6.9.1.1. Afterwards, the router performs a second lookup in the next hop table 20 with the IP address of the egress interface to determine the real next hop. In the example network of FIG. 1, this next hop address is determined as 8.2.1.1 (25). Thus, this forwarding packet operation requires two tables and two lookups. Once its status is ascertained, the packet is then transmitted to the router/end station indicated by the next hop lookup and the process is repeated until the packet is received by System 1 (34). If, for example, System 1 (at address 9.1.1.1) is moved so that it is connected to router RB instead of RC (for example, at 9.2.2.1), all router forwarding tables would then be updated to indicate RB as the next hop for System 1.
Thus, in current router operation, both tables 10, 20 are utilized when sending and receiving IP packets. BGP tables 10 are updated using the BGP protocol which enables routers to know the BGP structure of networks. Packet forwarding tables 20 are updated using the OSPF protocol, for example, which enables routers to understand the internal network architecture, i.e., within the autonomous network. OSPF calculates the shortest path from an IP Source Address (SA) to IP Destination Address (DA). For example, when a subnet is moved/deleted within a network, OSPF will update the new shortest path to that changed/deleted subnet if required (i.e., if associated next hop changes). This requires forwarding tables in all routers to be updated which entails deleting table entries and inserting new fields. The process of deleting and inserting new entries is not efficient. In addition, OSPF cannot account for local network structures when assembling routing table (i.e., OSPF is not aware of BGP routers).
It would be highly desirable to combine router forwarding and BGP tables into one table for more efficient processing and to have one router table that is hierarchy independent.
It is an object of the invention to provide a hierarchy independent routing table that comprises a combination of packet forwarding (Next hop) and BGP Lookup tables into one table for more efficient processing.
It is a further object of the invention to provide a hierarchy independent routing forwarding table implemented in network processor-based routing devices for reducing routing algorithm complexity.
According to the invention, there is provided an apparatus and method for routing packets in a network comprising one or more router devices, the method comprising the steps of: determining from a packet arrived at a router device a destination address for the packet; performing a look-up in a single packet forwarding table in the device to ascertain packet forwarding information comprising a subnet address associated with the destination address, an IP address of a router interface servicing the subnet address, and an associated flag indicating whether the router is a BGP exit router; forwarding the packet to the indicated IP address when the flag value is not set and, if said flag value is set, the steps of utilizing the indicated IP address as index to perform subsequent look-ups in the single packet forwarding table to find IP address of a next hop router and associated flag value, and forwarding the packet to the indicated next hop router upon first determination that the associated flag value is not set.
Advantageously, the single packet routing table and routing method of the invention promotes hierarchy independence so that packets may be routed between autonomous and external networks.